//面试题 02.04. 分割链表
/*给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* _head = new ListNode(-1, head);
        ListNode* left = _head;
        ListNode* pre = _head;
        ListNode* cur = head;
        while (cur && cur->val < x) {
            left = pre = cur;
            cur = cur->next;
        }
        while (cur) {
            if (cur->val < x) {
                pre->next = cur->next;
                cur->next = left->next;
                left->next = cur;
                left = left->next;
                cur = pre->next;
            } else {
                pre = cur;
                cur = cur->next;
            }
        }
        return _head->next;
    }
};


//LCR 027. 回文链表

/*给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse_list(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* n1 = nullptr;
        ListNode* n2 = head;
        ListNode* n3 = head->next;
        while (n2) {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
                n3 = n3->next;
        }
        // p->next = n1;
        return n1;
    }
    bool isPalindrome(ListNode* head) {
        ListNode* q = head;
        ListNode* s = head;
        while (q && q->next) {
            q = q->next;
            q = q->next;
            s = s->next;
        }
        // cout << s->val << endl;
        ListNode* n = reverse_list(s);
        ListNode* _head = head;
        while (_head != s) {
            if (n == nullptr || _head->val != n->val)
                return false;
            _head = _head->next;
            n = n->next;
        }
        return true;
    }
};

// O(1) 时间插入、删除和获取随机元素
/*实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。*/
class RandomizedSet {
    unordered_map<int, int> hash;
    vector<int> arr;

public:
    RandomizedSet() {}

    bool insert(int val) {
        if (hash.count(val))
            return false;
        else {
            arr.push_back(val);
            hash[val] = arr.size() - 1;
            return true;
        }
    }

    bool remove(int val) {
        if (hash.count(val)) {
            hash[arr[arr.size() - 1]] = hash[val];
            swap(arr[hash[val]], arr[arr.size() - 1]);
            arr.pop_back();
            hash.erase(val);
            return true;
        } else {
            return false;
        }
    }

    int getRandom() { return arr[rand() % arr.size()]; }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

 //除自身以外数组的乘积
 /*给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

 */
 class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int left_sum = 1;
        int right_sum = 1;
        vector<int> ret(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            ret[i] = left_sum;
            left_sum *= nums[i];
        }
        for (int i = nums.size() - 1; i >= 0; i--) {
            ret[i] *= right_sum;
            right_sum *= nums[i];
        }
        return ret;
    }
};

//加油站
/*在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。*/
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sum = 0;
        int cur = 0;
        int index = 0;
        for (int i = 0; i < gas.size(); i++) {
            sum += gas[i] - cost[i];
            cur += gas[i] - cost[i];
            if (cur < 0) {
                cur = 0;
                index = i + 1;
                index %= gas.size();
            }
        }
        return sum < 0 ? -1 : index;
    }
};